package com.hr.leetcode.链表;

/**
 * @author 周恒哲
 * @date 2020/04/29
 * 反转链表
 **/
public class _206_反转链表 {
    /**
     *解题思路：递归（从下往上看），假设我们 输入: 1->2->3->4->5->NULL，然后我们从5开始看，
     *我们创建一个新的临时链表来存储返回的数据new_list，当new_list=5,输出new_list=5,因为head的下
     *一个的为null了，然后我们继续递归new_list=4,
     *
     *
     */
    public ListNode reverseList(ListNode head) {
        //递归
        if(head==null || head.next==null){
            return head;
        }
        ListNode new_list=reverseList(head.next);//除了头结点外的其他都反转1->2<-3<-4<-5
        head.next.next=head;
        head.next=null;
        return new_list;
    }
    public ListNode reverseList1(ListNode head) {
        //三指针迭代遍历
        if(head==null){
            return head;
        }
        ListNode tail=null;
        ListNode first=head;
        ListNode second=head.next;
        while(first!=null){
            first.next=tail;//头节点的下一个节点是尾节点
            tail=first;   //尾节点变为头节点
            first=second;//让原先的第二个节点赋值给头节点
            if(second!=null){
                second=second.next;
            }
        }
        return tail;
    }
}